%Ejercicio 1
%valor(-X)
valor(mina).
valor(X) :- between(0,8,X).

%Ejercicio 2
%dim(+T, -Cols, -Fils)
dim([], _ , 0).
dim([F1|Fs], Cols, Fils) :- length(F1, Cols), length([F1|Fs], Fils).

%Ejercicio 3
%pos(+T, -Cols, -Fils)
pos(T, Cols, Fils) :- dim(T,C,F), between(1,F,Fils), between(1,C,Cols).

%Ejercicio 4: uso cut porque se que la respuesta es unica
%nonvars(?L, -R).
nonvars([],[]).
nonvars([X|L],[X|L2]) :- nonvar(X), nonvars(L,L2), !.
nonvars([X|L],L2) :- var(X), nonvars(L,L2).

%Ejercicio 5: usa el predicado anterior para obtener solo instanciados
%cant_minas(?L, -N)
cant_minas(L, N) :- nonvars(L, L2), minas(L2,N), !.

%minas(+L, -N): N es la cantidad de minas de una lista L de elementos instanciados
%Nota: la lista puede tener elementos no instanciados (habrá más de una solución 
%en ese caso), pero no es el uso que se le quiere dar.
minas([],0).
minas([mina|L], N) :- minas(L,N2), N is N2+1.
minas([X|L], N) :- X \== mina, minas(L,N).

%Ejercicio 6:
%vecinos(+T, +C, +F, ?L)
vecinos(T, C, F, L) :- bagof(V, vecino(T, C, F, V), L).

%vecino(+T, +C, +F, -V): da true sii V es un vecino
vecino(T, C, F, V) :- 	pos_vecina(C,F,Cv,Fv), elem(T, Cv, Fv, V).

%elem(+T, +C, +F, -E): da true sii E es el elemento de T en la posición (C,F)
elem(T, C, F, E) :- nth1(F, T, Fila), nth1(C, Fila, E).

%pos_vecina(+C,+F,-Cv,-Fv): da true sii (C,F) es posición vecina de (Cv,Fv)
pos_vecina(C,F,Cv,Fv) :- Fv is F - 1, Ci is C-1, Cf is C+1, between(Ci,Cf,Cv).
pos_vecina(C,F,Cv,F) :- Cv is C - 1.
pos_vecina(C,F,Cv,F) :- Cv is C + 1.
pos_vecina(C,F,Cv,Fv) :- Fv is F + 1, Ci is C-1, Cf is C+1, between(Ci,Cf,Cv).

%Ejercicio 7:
%consistente(+T, +C, +F)
%Caso 1: es una mina
consistente(T, C, F) :- elem(T, C, F, mina), !.
%Caso 2: es el numero de minas que hay en su vecindad
consistente(T, C, F) :- elem(T, C, F, N), vecinos(T,C,F,L), cant_minas(L,N).

%Ejercicio 8:
%consistente(+T)
consistente(T) :- not(inconsistente(T)).
%inconsistente(+T): el cut es para termine apenas encuentra una posición inconsistente 
inconsistente(T) :- pos(T, C, F), not(consistente(T, C, F)), !.

%Ejercicio 9:
%completarA(?T)
completarA(T) :- instanciarTablero(T), consistente(T).

%instanciarTablero(?T).
instanciarTablero([]).
instanciarTablero([F|FS]) :- instanciarFila(F), instanciarTablero(FS).
%instanciarFila(?T).
instanciarFila([]).
instanciarFila([X|XS]) :- valor(X), instanciarFila(XS).

%Ejercicio 10:
completarB(T) :- posiciones(T,Ps), instanciarCons(T,Ps),
    dim(T,C,F), consistente(T,C,F).
%verifica borde derecho inferior al final ya que instanciarCons lo hace para
% el resto de las celdas

%posiciones(+T, -Ps): Devuelve una lista de las posiciones recorridas en orden
%de izq a der, de arriba a abajo
posiciones(T, Ps) :- bagof(P, posicion(T,P), Ps).
%posicion(+T, -P): igual al predicado pos, pero con la forma par(C,F)
posicion(T, par(C,F)) :- pos(T,C,F).
%el orden está determinado por la definición de pos (ej 3)
%ejemplo:
%?- posicion([[_,_,_],[_,_,_]],P).
%P = par(1, 1) ;
%P = par(2, 1) ;
%P = par(3, 1) ;
%P = par(1, 2) ;
%P = par(2, 2) ;
%P = par(3, 2).
%?- posiciones([[_,_,_],[_,_,_]],Ps).
%Ps = [par(1, 1), par(2, 1), par(3, 1), par(1, 2), par(2, 2), par(3, 2)].

%instanciarCons(?T, +Ps): Recibe un tablero con posiciones sin instanciar y una
% lista de sus posiciones.
%Recorre las pociones instanciando en el mismo orden verificando la consistencia de la
% celda superior izquierda (y alguna otra en el caso de los bordes).
instanciarCons(_, []).
instanciarCons(T, [par(C,F)|Ps]) :- elem(T,C,F,E), valor(E),
    Cm1 is C-1, Fm1 is F-1, verificar(T,Cm1,Fm1),
    verificarBD(T,C,Fm1), verificarBI(T,Cm1,F), instanciarCons(T,Ps).

%verificar(+T,+C,+F) sii (C,F) es posicion valida y es consistente
%Nota: si bien el tablero puede no estar instanciado totalmente se cuida que las 
%posiciones vecinas lo estén.
verificar(T,C,F) :- not(pos(T,C,F)), !. %no es posicion
verificar(T,C,F) :- consistente(T,C,F). %es posicion valida, verifica consistencia
%verificarBD(T,C,_) para verificar consistencia si es un borde derecho
verificarBD(T,C,_) :- not(dim(T,C,_)),!. %no es borde derecho
verificarBD(T,C,F) :- verificar(T,C,F). %es borde
%verificarBI(T,_,F) para verificar consistencia si es un borde inferior
verificarBI(T,_,F) :- not(dim(T,_,F)),!. %no es borde inferior
verificarBI(T,C,F) :- verificar(T,C,F). %es borde
%ejemplos:
%?- verificar([[1,1],[1,mina]],1,1).
%true.
%?- verificar([[2,1],[1,mina]],1,1).
%false.

%Ejercicio 11:
%completarC(?T)
completarC(T) :- posiciones(T,Ps), instanciarValCons(T,Ps),
    dim(T,C,F), consistente(T,C,F). %verifica borde derecho inferior

%valorValido(?T,+C,+F,-X) sii X es un valor consistente de acuerdo al criterio del ej 11
%Caso 1: si es mina no puede tener un vecino instanciado en 0 
valorValido(T,C,F,mina) :- vecinos(T,C,F,Vs), nonvars(Vs,Vs2), not(member(0,Vs2)).
%Caso 2: si es número, esta acotado por la cantidad de minas vecinas instanciadas, y por
% la cantidad máxima de minas que puede llegar a tener (sumando las celdas no instanciadas)
valorValido(T,C,F,X) :- vecinos(T,C,F,Vs), cant_minas(Vs,M), n_vars(Vs,N),
    valor(X), X \== mina, X >= M, M2 is M + N, X =< M2.
%ejemplo:
%?- valorValido([[1,mina],[_,_]],1,2,X).
%X = mina ;
%X = 1 ;
%X = 2 ;
%false.

%n_vars(?L,-N): true sii N es la cantidad de variables sin instanciar de L (en el mismo orden)
n_vars([],0).
n_vars([X|L], N) :- var(X), n_vars(L, N2), N is N2 + 1, !. %el resultado es único
n_vars([X|L], N) :- nonvar(X), n_vars(L, N).

%instanciarValCons(?T, +Ps): true sii T resulta de instanciar las posiciones de Ps (completarC)
%igual a instanciarCons pero los valores estan limitados segun el predicado valorValido
instanciarValCons(_, []).
instanciarValCons(T, [par(C,F)|Ps]) :- elem(T,C,F,E), valorValido(T,C,F,E),
    Cm1 is C-1, Fm1 is F-1, verificar(T,Cm1,Fm1),
    verificarBD(T,C,Fm1), verificarBI(T,Cm1,F), instanciarValCons(T,Ps).

%Ejercicio 13 
%completar(?T)
completar(T) :- posiciones(T,Ps), instanciarValCons2(T,Ps),
    dim(T,C,F), consistente(T,C,F). %verifica borde derecho inferior

%instanciarValCons2(?T, +Ps) agrega al anterior una verifición similar a la que limita los
% valores válidos en completarC, pero para los vecinos de la celda que ya estén instanciados
% en un valor numérico. La motivación es que se puedan limitar aún más los valores para la celda
% que se está instanciando. (El vecino (C-1,F-1) no necesita esta verificación)
instanciarValCons2(_, []).
instanciarValCons2(T, [par(C,F)|Ps]) :- elem(T,C,F,E), valorValido(T,C,F,E),
    Cm1 is C-1, Fm1 is F-1, verificar(T,Cm1,Fm1),
    verificarBD2(T,C,Fm1), verificarBI2(T,Cm1,F), 
    CM1 is C+1, FM1 is F+1, verificarSiNum(T,Cm1,FM1),
    verificarSiNum(T,C,FM1),verificarSiNum(T,CM1,FM1), 
    verificarSiNum(T,CM1,F), verificarSiNum(T,CM1,Fm1),
    instanciarValCons2(T,Ps).

%verificarSiNum(?T,+C,+F) true sii no es posicion, o el elmento no esta instanciado,
% o es mina, o es numero parcialmente consistente (sus vecinos pueden no estar instanciados)
verificarSiNum(T,C,F) :- not(pos(T,C,F)), !. %o no es posicion
verificarSiNum(T,C,F) :- elem(T,C,F,E), var(E), !. %o es variable (no puedo ver consistencia)	
verificarSiNum(T,C,F) :- elem(T,C,F,mina), !. %o es mina, no me interesa verlo por ahora
verificarSiNum(T,C,F) :- elem(T,C,F,E), vecinos(T,C,F,Vs), cant_minas(Vs,M), n_vars(Vs,N),
	E >= M, M2 is M + N, E =< M2. %o es valor valido instanciado

%verificarBD2(?T,+C,+F): si es un borde derecho se debe verificar consistencia sabiendo
% que todos los vecinos están instanciados, si no se debe usar el predicado anterior
verificarBD2(T,C,F) :- dim(T,C,_), verificar(T,C,F), !. %es borde derecho
verificarBD2(T,C,F) :- verificarSiNum(T,C,F). %no es borde
%similar al anterior, pero para borde inferior
verificarBI2(T,C,F) :- dim(T,_,F), verificar(T,C,F), !. %es borde inferior
verificarBI2(T,C,F) :- verificarSiNum(T,C,F). %no es borde

%Fin de los ejercicios

pre_r(N,T) :- get_time(T1), stamp_date_time(T1, X1, 'UTC'), write(X1), nl, problem(N,T).
post_r(T) :- mostrar(T), get_time(T2), stamp_date_time(T2, X2, 'UTC'), write(X2), nl.

rA(N,T) :- pre_r(N,T), completarA(T), post_r(T).
rB(N,T) :- pre_r(N,T), completarB(T), post_r(T).
rC(N,T) :- pre_r(N,T), completarC(T), post_r(T).
rD(N,T) :- pre_r(N,T), completar(T), post_r(T).

mostrar([]).
mostrar([Fila|T]) :-
	mostrar_lista(Fila),
	mostrar(T).

mostrar_lista([]) :- nl.
mostrar_lista([H|T]) :- mostrar_celda(H), mostrar_lista(T).

mostrar_celda(C) :- nonvar(C), C == mina, write('*').
mostrar_celda(C) :-	nonvar(C), C \= mina, write(C).
mostrar_celda(C) :- var(C), write('_').


problem(t1, [[_,_],
			 [_,1]]).

problem(t2, [[_,_],
			 [_,2]]).

problem(t3, [[_,_],
			 [_,3]]).

problem(t4, [[0,_,_],
			 [_,1,_],
			 [_,_,0]]).

% Problem from Gecode/examples/minesweeper.cc  problem 0
%
% Solution:
%  1 0 0 0 0 1
%  0 1 0 1 1 0
%  0 0 0 0 1 0
%  0 0 0 0 1 0
%  0 1 1 1 0 0
%  1 0 0 0 1 1
%
problem(0,[[_,_,2,_,3,_],
           [2,_,_,_,_,_],
           [_,_,2,4,_,3],
           [1,_,3,4,_,_],
           [_,_,_,_,_,3],
           [_,3,_,3,_,_]]).



% Problem from Gecode/examples/minesweeper.cc  problem 1
problem(1,[[_,2,_,2,1,1,_,_],
           [_,_,4,_,2,_,_,2],
           [2,_,_,2,_,_,3,_],
           [2,_,2,2,_,3,_,3],
           [_,_,1,_,_,_,4,_],
           [1,_,_,_,2,_,_,3],
           [_,2,_,2,2,_,3,_],
           [1,_,1,_,_,1,_,1]]).



% Problem from Gecode/examples/minesweeper.cc  problem 2
problem(2,[[1,_,_,2,_,2,_,2,_,_],
           [_,3,2,_,_,_,4,_,_,1],
           [_,_,_,1,3,_,_,_,4,_],
           [3,_,1,_,_,_,3,_,_,_],
           [_,2,1,_,1,_,_,3,_,2],
           [_,3,_,2,_,_,2,_,1,_],
           [2,_,_,3,2,_,_,2,_,_],
           [_,3,_,_,_,3,2,_,_,3],
           [_,_,3,_,3,3,_,_,_,_],
           [_,2,_,2,_,_,_,2,2,_]]).


% Problem from Gecode/examples/minesweeper.cc  problem 3
problem(3,[[2,_,_,_,3,_,1,_],
           [_,5,_,4,_,_,_,1],
           [_,_,5,_,_,4,_,_],
           [2,_,_,_,4,_,5,_],
           [_,2,_,4,_,_,_,2],
           [_,_,5,_,_,4,_,_],
           [2,_,_,_,5,_,4,_],
           [_,3,_,3,_,_,_,2]]).


% Problem from Gecode/examples/minesweeper.cc  problem 4
problem(4,[[0,_,0,_,1,_,_,1,1,_],
           [1,_,2,_,2,_,2,2,_,_],
           [_,_,_,_,_,_,2,_,_,2],
           [_,2,3,_,1,1,_,_,_,_],
           [0,_,_,_,_,_,_,2,_,1],
           [_,_,_,2,2,_,1,_,_,_],
           [_,_,_,_,_,3,_,3,2,_],
           [_,5,_,2,_,_,_,3,_,1],
           [_,3,_,1,_,_,3,_,_,_],
           [_,2,_,_,_,1,2,_,_,0]]).


% Problem from Gecode/examples/minesweeper.cc  problem 5
problem(5,[[_,2,1,_,2,_,2,_,_,_],
           [_,4,_,_,3,_,_,_,5,3],
           [_,_,_,4,_,4,4,_,_,3],
           [4,_,4,_,_,5,_,6,_,_],
           [_,_,4,5,_,_,_,_,5,4],
           [3,4,_,_,_,_,5,5,_,_],
           [_,_,4,_,4,_,_,5,_,5],
           [2,_,_,3,3,_,6,_,_,_],
           [3,6,_,_,_,3,_,_,4,_],
           [_,_,_,4,_,2,_,2,1,_]]).



% Problem from Gecode/examples/minesweeper.cc  problem 6
problem(6,[[_,3,2,_,_,1,_,_],
           [_,_,_,_,1,_,_,3],
           [3,_,_,2,_,_,_,4],
           [_,5,_,_,_,5,_,_],
           [_,_,6,_,_,_,5,_],
           [3,_,_,_,5,_,_,4],
           [2,_,_,5,_,_,_,_],
           [_,_,2,_,_,3,4,_]]).


% Problem from Gecode/examples/minesweeper.cc  problem 7
problem(7,[[_,1,_,_,_,_,_,3,_],
           [_,_,_,3,4,3,_,_,_],
           [2,4,4,_,_,_,4,4,3],
           [_,_,_,4,_,4,_,_,_],
           [_,4,_,4,_,3,_,6,_],
           [_,_,_,4,_,3,_,_,_],
           [1,2,3,_,_,_,1,3,3],
           [_,_,_,3,2,2,_,_,_],
           [_,2,_,_,_,_,_,3,_]]).



% Problem from Gecode/examples/minesweeper.cc  problem 8
problem(8,[[_,_,_,_,_,_,_],
           [_,2,3,4,3,5,_],
           [_,1,_,_,_,3,_],
           [_,_,_,5,_,_,_],
           [_,1,_,_,_,3,_],
           [_,1,2,2,3,4,_],
           [_,_,_,_,_,_,_]]).


% Problem from Gecode/examples/minesweeper.cc  problem 9
problem(9,[[2,_,_,_,2,_,_,_,2],
           [_,4,_,4,_,3,_,4,_],
           [_,_,4,_,_,_,1,_,_],
           [_,4,_,3,_,3,_,4,_],
           [2,_,_,_,_,_,_,_,2],
           [_,5,_,4,_,5,_,4,_],
           [_,_,3,_,_,_,3,_,_],
           [_,4,_,3,_,5,_,6,_],
           [2,_,_,_,1,_,_,_,2]]).



% From "Some Minesweeper Configurations",page 2
problem(10,[[_,_,_,_,_,_],
            [_,2,2,2,2,_],
            [_,2,0,0,2,_],
            [_,2,0,0,2,_],
            [_,2,2,2,2,_],
            [_,_,_,_,_,_]]).



% From "Some Minesweeper Configurations",page 3
% 4 solutions
problem(11,[[2,3,_,2,2,_,2,1],
            [_,_,4,_,_,4,_,2],
            [_,_,_,_,_,_,4,_],
            [_,5,_,6,_,_,_,2],
            [2,_,_,_,5,5,_,2],
            [1,3,4,_,_,_,4,_],
            [0,1,_,4,_,_,_,3],
            [0,1,2,_,2,3,_,2]]).


% Richard Kaye: How Complicated is Minesweeper?
% http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ASE2003.pdf
%
% A Wire,page 33
% 2 solutions
%
problem(12,[[_,0,0,0,0,0,0,0,0,0,0,0,0,_],
            [_,1,1,1,1,1,1,1,1,1,1,1,1,_],
            [_,_,1,_,_,1,_,_,1,_,_,1,_,_],
            [_,1,1,1,1,1,1,1,1,1,1,1,1,_],
            [_,0,0,0,0,0,0,0,0,0,0,0,0,_]]).


% Richard Kaye: How Complicated is Minesweeper?
% http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ASE2003.pdf
% A splitter,page 35
% Many solutions...
%
problem(13,[[_,_,_,0,_,_,_,0,_,_,_],
            [_,_,_,0,1,_,1,0,_,_,_],
            [_,_,_,0,1,_,1,0,_,_,_],
            [0,0,0,0,1,1,1,0,0,0,0],
            [_,1,1,1,1,_,1,1,1,1,_],
            [_,_,_,1,_,2,_,1,_,_,_],
            [_,1,1,1,1,_,1,1,1,1,_],
            [0,0,0,0,1,1,1,0,0,0,0],
            [_,_,_,0,1,_,1,0,_,_,_],
            [_,_,_,0,1,_,1,0,_,_,_],
            [_,_,_,0,_,_,_,0,_,_,_]]).



% Oleg German,Evgeny Lakshtanov: "Minesweeper" without a computer
% http://arxiv.org/abs/0806.3480,page 4
problem(14,[[_,1,_,1,_,1],
            [2,_,2,_,1,_],
            [_,3,_,2,_,1],
            [1,_,3,_,2,_],
            [_,1,_,2,_,1]]).
